#include "PageCache.h"

PageCache PageCache::_sInst;

// 获取从对象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{
	// 先算页号
	PAGE_ID id = ((PAGE_ID)obj >> PAGE_SHIFT);
	auto ret = _idSpanMAp.find(id);

	if (ret != _idSpanMAp.end())
	{
		// 找到了返回映射的span（指针）
		return ret->second;
	}
	else
	{
		// 理论上不可能找不到
		assert(false);
		return nullptr;
	}

}

// 释放空闲span回到Page Cache，并合并相邻的页
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	// 内碎片解决不了得要忍受，但是外碎片可以通过合并页来解决，将好几个空闲的页合并为一个大页（申请8page -> 如果连续则合并1page）
	// 对span前后的页，尝试进行合并，缓解内存碎片问题
	// 这里在上层就已经加了锁了

	// 向前合并
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		auto ret = _idSpanMAp.find(prevId);
		// 前面的页号没有，不合并了
		if (ret == _idSpanMAp.end())
		{
			break;
		}

		// 前面相邻的span在使用，不合并了
		Span* prevSpan = ret->second;
		if (prevSpan->_isUse == true)
		{
			break;
		}

		// 合并出超过128页的span没办法管理，不合并了
		if (prevSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}

		// 走到这就可以开始合并了
		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while (1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMAp.find(nextId);
		if (ret == _idSpanMAp.end())
		{
			break;
		}

		Span* nextSpan = ret->second;
		if (nextSpan->_isUse == true)
		{
			break;
		}

		if (nextSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;

	// 将首尾存入map
	_idSpanMAp[span->_pageId] = span;
	_idSpanMAp[span->_pageId + span->_n - 1] = span;
}

// 获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 不能用桶锁，因为如果k桶没有对象则要把k ~ 128都遍历一遍，桶锁是锁不住的，效率会比较低（涉及到频繁的加锁解锁问题）
	// 锁的话因为递归调用自己的问题，所以会死锁，两个解决方案：1、递归锁 2、分离一个子函数出来（弄成非递归式）


	// 先检查第k个桶里面有没有span,有的话就弹一个出去
	if (!_spanLists[k].Empty())
	{
		return _spanLists->PopFront();
	}

	// 检查一下后面的桶里面有没有span，如果有可以把它进行切分
	for (size_t i = k + 1; i < NPAGES; ++i) 
	{
		if (!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			// 在nSpan的头部切一个k页下来
			// k页span返回
			// nspan再挂到对应映射的位置
			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			// 切走了k页还剩x页，所以要挂回x页的位置：
			_spanLists[nSpan->_n].PushFront(nSpan);
			// 存储nSpan的首尾页号跟nSpan映射,方便page cache回收内存时进行合并查找（首尾页的意思看下）
			_idSpanMAp[nSpan->_pageId] = nSpan;
			// 为什么要-1：例如ID为1000， n为5， 那么最后一页应该是1004，所以要-1,(1000 + 5 - 1 = 1004)
			_idSpanMAp[nSpan->_pageId + nSpan->_n - 1] = nSpan;


			// 设置页数与Span的映射
			// 建立id和span的映射，方便central cache回收小块内存时，查找对应的span
			for (PAGE_ID i = 0; i < kSpan->_n; i++)
			{
				_idSpanMAp[kSpan->_pageId + i] = kSpan;
			}

			return kSpan;
		}
	}

	// 走到这个位置就说明后面没有大页的span了
	// 这时就要去找堆要一个128页的span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	
	// 知道地址算页号：飞书
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1; // 因为申请的就是128页,但是不要直接写128，因为万一你想把桶加大呢？

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k); // 再递归的调用自己即可

	// 这里可能会有一个小问题，就是有人说想直接复用上面的逻辑，因为递归调用慢了，还要从k走到128
	// 虽然确实会慢一点，但是也就一百来次，计算机太快了，所以几乎都可以忽略不计,所以不用去考虑这种芝麻量的事
	// 所以代码的复用很重要，因为如果某个细节错乱，那两个地方还都得改动
}

